package LeetCode热题HOT100;

import 力扣题库.TreeNode;

public class p543二叉树的直径 {
    int curMaxDeepth=0;
    public int diameterOfBinaryTree(TreeNode root) {
        //深度优先搜索：利用递归函数对目标进行遍历
        deepth(root);
        return curMaxDeepth;
        //最终返回的二叉树的直径，即任意两节点最短路径的最大值，最短路径是指 两节点之间边的数目
    }


    private int deepth(TreeNode rt) {
        //遍历节点深度的同时，要根据当前节点左右子树深度之和判断当前直径是否更新
        if (rt==null) {
            return 0;
        }

        int leftDeep=deepth(rt.left);
        int rightDeep=deepth(rt.right);
        if (leftDeep+rightDeep > curMaxDeepth) {
            //更新当前直径
            curMaxDeepth = leftDeep+rightDeep;
        }
        return Math.max(leftDeep,rightDeep)+1;
    }
}
